package algorithmic_data_structure.动态规划;

import org.junit.Test;

import java.util.ArrayList;

public class 最少硬币数 {
    @Test
    public void test(){
//        System.out.println(minCoins(new int[]{1, 2, 3, 4}, 10));
//        System.out.println(minCoins(new int[]{1, 2, 3, 4}, 8));
//        System.out.println(minCoins(new int[]{1, 2, 3, 4}, 19));
        System.out.println(minCoins(new int[]{154, 212, 365, 499}, 2000));
        System.out.println(minCoins(new int[]{154, 212, 365, 499}, 1));
        System.out.println(minCoins(new int[]{28 ,19 ,26}, 16));
    }
    public static int minCoins(int[] arr, int aim) {
        if (aim == 0) {
            return 0;
        }
//        return process(arr,0,aim,new ArrayList<String>());
        return dp(arr,aim);
    }

    private static int dp(int[] arr, int aim) {
        if (aim == 0){
            return 0;
        }
        int[][] dp = new int[arr.length + 1][aim + 1];
        dp[arr.length][0] = 0;
        for (int i = 1; i <= aim; i++) {
            dp[arr.length][i] = Integer.MAX_VALUE;
        }
        for (int index = arr.length-1; index >= 0; index--) {
            for (int rest = aim; rest >= 0; rest--) {
                int res = Integer.MAX_VALUE;
                for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
                    int p = dp[index+1][rest - zhang * arr[index]];
                    if (p != Integer.MAX_VALUE){
                        res = Math.min(p + zhang,res);
                    }
                }
                dp[index][rest] = res;
            }
        }
        return dp[0][aim];
    }
    private static int process(int[] arr, int index, int aim, ArrayList<String> list) {
        if (arr.length == index){
            return aim == 0 ? 0 : Integer.MAX_VALUE;
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i * arr[index] <= aim; i++) {
//            list.add(" " + i + "*" + arr[index]);
            int p = process(arr,index+1,aim - i * arr[index], list);
//            list.remove(list.size()-1);
            if (p != Integer.MAX_VALUE){
                res = Math.min(p + i,res);
            }
        }
        return res;
    }
}
